﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;

using System.Diagnostics;

namespace Projektarbete
{
    class Node
    {
        public MovementDirection parentMovementDirection;
        public Node parent;

        public Point position;

        public int gScore;
        public int hScore;
        public int fScore;

        public Node(Point position, Point toPosition, int gScore)
        {
            this.position = position;
            this.gScore = gScore;

            hScore = Pathfinding.GetManhattanDistance(this.position, toPosition);

            fScore = this.gScore + hScore;

            parentMovementDirection = MovementDirection.none;
        }

        public Node(Point position, Point toPosition, int gScore, MovementDirection parentMovementDirection, Node parent)
        {
            this.position = position;
            this.gScore = gScore;

            hScore = Pathfinding.GetManhattanDistance(this.position, toPosition);

            fScore = this.gScore + this.hScore;

            this.parentMovementDirection = parentMovementDirection;
            this.parent = parent;
        }

        public void UpdateFScore(int gScore, int hScore)
        {
            this.gScore = gScore;
            this.hScore = hScore;

            fScore = this.gScore + this.hScore;
        }
    }

    class ArrayNode
    {
        public MovementDirection parentMovementDirection;
        public ArrayNode parent;

        public Point position;

        public int gScore;
        public int hScore;
        public int fScore;

        private bool closedList;
        private bool openList;

        public bool isInClosedList
        {
            get { return closedList; }
            set
            {
                openList = false;
                closedList = true;
            }
        }

        public bool isInOpenList
        {
            get { return openList; }
            set
            {
                openList = true;
                closedList = false;
            }
        }

        public ArrayNode(Point position, Point toPosition, int gScore)
        {
            this.position = position;
            this.gScore = gScore;

            hScore = Pathfinding.GetManhattanDistance(this.position, toPosition);

            fScore = this.gScore + hScore;

            parentMovementDirection = MovementDirection.none;
        }

        public ArrayNode(Point position, Point toPosition, int gScore, MovementDirection parentMovementDirection, ArrayNode parent)
        {
            this.position = position;
            this.gScore = gScore;

            hScore = Pathfinding.GetManhattanDistance(this.position, toPosition);

            fScore = this.gScore + this.hScore;

            this.parentMovementDirection = parentMovementDirection;
            this.parent = parent;
        }

        public void UpdateFScore(int gScore, int hScore)
        {
            this.gScore = gScore;
            this.hScore = hScore;

            fScore = this.gScore + this.hScore;
        }
    }

    static class Pathfinding
    {
        /// <summary>
        /// Pathfind a way to the given position (using manhattan-distance). Returns an empty list if none is found
        /// </summary>
        /// <param name="toPosition">position to pathfind to AS A TILE POSITION</param>
        /// <param name="fromPosition">position to pathfind to AS A TILE POSITION</param>
        /// <returns>Tell David if you can see this</returns>
        public static LinkedList<MovementDirection> AStar(Point fromPosition, Point toPosition)
        {
            Stopwatch time = new Stopwatch();
            time.Start();
            //TODO: IF PATH NOT FOUND
            //LinkedList<ArrayNode> closedList = new LinkedList<ArrayNode>();
            LinkedList<ArrayNode> openList = new LinkedList<ArrayNode>();

            ArrayNode[][] nodes = new ArrayNode[MapHandler.mapDimensions.Y][];

            for (int y = 0; y < MapHandler.mapDimensions.Y; y++)
            {
                nodes[y] = new ArrayNode[MapHandler.mapDimensions.X];
            }

            ArrayNode currentNode = new ArrayNode(fromPosition, toPosition, 0);

            currentNode.parent = new ArrayNode(Point.Zero, Point.Zero, -1);

            openList.AddLast(currentNode);
            nodes[currentNode.position.Y][currentNode.position.X] = currentNode;
            nodes[currentNode.position.Y][currentNode.position.X].isInOpenList = true;

            Point[] values = new Point[4] { new Point(0, -1), new Point(0, 1), new Point(-1, 0), new Point(1, 0) };

            while (true)
            {
                int lowestFSCore = int.MaxValue;

                LinkedList<ArrayNode> tempList = new LinkedList<ArrayNode>();

                foreach (ArrayNode node in openList)
                {
                    if (node.fScore <= lowestFSCore)
                    {
                        lowestFSCore = node.fScore;
                        currentNode = node;
                    }
                }

                if (lowestFSCore == int.MaxValue)
                    return new LinkedList<MovementDirection>(); //Ingen väg hittades. Skicka tom linkedList (annars yrar snubben omkring)

                if (currentNode.position == toPosition)
                    break;

                openList.Remove(currentNode);

                nodes[currentNode.position.Y][currentNode.position.X].isInClosedList = true;

                Point tempPosition;
                for (byte x = 0; x < 4; x++)
                {
                    tempPosition = new Point(currentNode.position.X + values[x].X, currentNode.position.Y + values[x].Y);

                    if (!Collision.TestCollision(MapHandler.map[tempPosition.Y][tempPosition.X].getTextureID))
                    {
                        if (nodes[tempPosition.Y][tempPosition.X] != null)
                        {
                            if (nodes[tempPosition.Y][tempPosition.X].isInClosedList && nodes[tempPosition.Y][tempPosition.X].gScore <= currentNode.gScore)
                            {
                                nodes[tempPosition.Y][tempPosition.X].UpdateFScore(currentNode.gScore + 1, GetManhattanDistance(tempPosition, toPosition));
                            }
                            else if (nodes[tempPosition.Y][tempPosition.X].isInOpenList && nodes[tempPosition.Y][tempPosition.X].gScore <= currentNode.gScore)
                            {
                                nodes[tempPosition.Y][tempPosition.X].UpdateFScore(currentNode.gScore + 1, GetManhattanDistance(tempPosition, toPosition));
                            }
                        }
                        else
                        {
                            nodes[tempPosition.Y][tempPosition.X] = new ArrayNode(tempPosition, toPosition, currentNode.gScore + 1, getMovementDirection(x), nodes[currentNode.position.Y][currentNode.position.X]);
                            nodes[tempPosition.Y][tempPosition.X].isInOpenList = true;

                            openList.AddFirst(nodes[tempPosition.Y][tempPosition.X]);
                        }
                    }
                }
            }

            LinkedList<MovementDirection> returnList = new LinkedList<MovementDirection>();

            while (true)
            {
                if (currentNode.parentMovementDirection != MovementDirection.none)
                    returnList.AddFirst(currentNode.parentMovementDirection);
                else
                    break;

                currentNode = currentNode.parent;
            }

            time.Stop();
            Debug.WriteLine("PATHFIND TIME: " + time.ElapsedTicks.ToString());

            return returnList;
        }

        /// <summary>
        /// Pathfind a way to the given position (using manhattan-distance). If the player can not see a tile, the search will be off
        /// </summary>
        /// <param name="toPosition">position to pathfind to AS A TILE POSITION</param>
        /// <param name="fromPosition">position to pathfind to AS A TILE POSITION</param>
        /// <returns>Tell David if you can see this</returns>
        public static LinkedList<MovementDirection> AStarWithVision(Point fromPosition, Point toPosition)
        {
            Stopwatch time = new Stopwatch();
            time.Start();

            if (!Global.CanPlayerSee(toPosition)) //Om spelaren inte kan se positionen som den försöker gå till
                return new LinkedList<MovementDirection>();

            LinkedList<ArrayNode> openList = new LinkedList<ArrayNode>();

            Random random = Global.random;

            ArrayNode[][] nodes = new ArrayNode[MapHandler.mapDimensions.Y][];

            for (int y = 0; y < MapHandler.mapDimensions.Y; y++)
            {
                nodes[y] = new ArrayNode[MapHandler.mapDimensions.X];
            }

            ArrayNode currentNode = new ArrayNode(fromPosition, toPosition, 0);

            currentNode.parent = new ArrayNode(Point.Zero, Point.Zero, -1);

            openList.AddLast(currentNode);
            nodes[currentNode.position.Y][currentNode.position.X] = currentNode;
            nodes[currentNode.position.Y][currentNode.position.X].isInOpenList = true;

            Point[] values = new Point[4] { new Point(0, -1), new Point(0, 1), new Point(-1, 0), new Point(1, 0) };

            while (true)
            {
                int lowestFSCore = int.MaxValue;

                LinkedList<ArrayNode> tempList = new LinkedList<ArrayNode>();

                foreach (ArrayNode node in openList)
                {
                    if (node.fScore <= lowestFSCore)
                    {
                        lowestFSCore = node.fScore;
                        currentNode = node;
                    }
                }

                if (lowestFSCore == int.MaxValue)
                    return new LinkedList<MovementDirection>(); //Ingen väg hittades. Skicka tom linkedList (annars yrar snubben omkring)

                if (currentNode.position == toPosition)
                    break;

                openList.Remove(currentNode);

                nodes[currentNode.position.Y][currentNode.position.X].isInClosedList = true;

                Point tempPosition;

                List<Point> availableMovementDirections = new List<Point>();
                List<byte> xValue = new List<byte>();
                for (byte x = 0; x < 4; x++)
                {
                    tempPosition = new Point(currentNode.position.X + values[x].X, currentNode.position.Y + values[x].Y);

                    if (Global.CanPlayerSee(tempPosition)) //Kolla om spelaren kan se tilen
                    {
                        if (!Collision.TestCollision(MapHandler.map[tempPosition.Y][tempPosition.X].getTextureID))
                        {
                            if (nodes[tempPosition.Y][tempPosition.X] != null)
                            {
                                if (nodes[tempPosition.Y][tempPosition.X].isInClosedList && nodes[tempPosition.Y][tempPosition.X].gScore <= currentNode.gScore)
                                {
                                    nodes[tempPosition.Y][tempPosition.X].UpdateFScore(currentNode.gScore + 1, GetManhattanDistance(tempPosition, toPosition));
                                }
                                else if (nodes[tempPosition.Y][tempPosition.X].isInOpenList && nodes[tempPosition.Y][tempPosition.X].gScore <= currentNode.gScore)
                                {
                                    nodes[tempPosition.Y][tempPosition.X].UpdateFScore(currentNode.gScore + 1, GetManhattanDistance(tempPosition, toPosition));
                                }
                            }
                            else
                            {
                                //nodes[tempPosition.Y][tempPosition.X] = new ArrayNode(tempPosition, toPosition, currentNode.gScore + 1, getMovementDirection(x), nodes[currentNode.position.Y][currentNode.position.X]);
                                //nodes[tempPosition.Y][tempPosition.X].isInOpenList = true;

                                //openList.AddFirst(nodes[tempPosition.Y][tempPosition.X]);
                                xValue.Add(x);
                                availableMovementDirections.Add(tempPosition);
                            }
                        }
                    }
                }
                while (availableMovementDirections.Count > 0)
                {
                    int nextRandom = random.Next(0, availableMovementDirections.Count);

                    tempPosition = availableMovementDirections.ElementAt(nextRandom);

                    nodes[tempPosition.Y][tempPosition.X] = new ArrayNode(tempPosition, toPosition, currentNode.gScore + 1, getMovementDirection(xValue.ElementAt(nextRandom)), nodes[currentNode.position.Y][currentNode.position.X]);
                    nodes[tempPosition.Y][tempPosition.X].isInOpenList = true;

                    openList.AddFirst(nodes[tempPosition.Y][tempPosition.X]);

                    availableMovementDirections.RemoveAt(nextRandom);
                    xValue.RemoveAt(nextRandom);
                }
            }

            LinkedList<MovementDirection> returnList = new LinkedList<MovementDirection>();

            while (true)
            {
                if (currentNode.parentMovementDirection != MovementDirection.none)
                    returnList.AddFirst(currentNode.parentMovementDirection);
                else
                    break;

                currentNode = currentNode.parent;
            }

            time.Stop();
            Debug.WriteLine("PATHFIND TIME: " + time.ElapsedTicks.ToString());

            return returnList;
        }

        private static MovementDirection getMovementDirection(byte x)
        {
            if (x == 0)
                return MovementDirection.up;
            else if (x == 1)
                return MovementDirection.down;
            else if (x == 2)
                return MovementDirection.left;
            else
                return MovementDirection.right;
        }

        private static MovementDirection negateMovementDirection(MovementDirection movementDirection)
        {
            if (movementDirection == MovementDirection.up)
                return MovementDirection.down;
            else if (movementDirection == MovementDirection.down)
                return MovementDirection.up;
            else if (movementDirection == MovementDirection.left)
                return MovementDirection.right;
            else
                return MovementDirection.left;
        }

        public static int GetManhattanDistance(Point fromPosition, Point toPosition)
        {
            return Math.Abs(toPosition.X - fromPosition.X) + Math.Abs(toPosition.Y - fromPosition.Y);
        }
    }
}
